package 剑指专题.搜索算法;


/*
 * Author：江松
 * Date：2023/3/31 21:28
 *
 矩阵中的路径：
 1，dfs
 */

public class Main7 {

    private boolean vis[][];
    private int dx[]={0,0,1,-1};
    private int dy[]={1,-1,0,0};
    private boolean res;
    private char[][]matrix;
    private String word;

    public void dfs(int x,int y,int now){
        if(word.charAt(now)!=matrix[x][y])return;
        if(now==word.length()-1){
            res=true;
            return;
        }
        for(int i=0;i<4;++i){
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(xx>=0&&xx<matrix.length&&yy>=0&&yy<matrix[0].length&&!vis[xx][yy]){
                vis[xx][yy]=true;
                dfs(xx,yy,now+1);
                vis[xx][yy]=false;
            }
        }
    }

    public boolean hasPath (char[][] matrix, String word) {
        if(matrix.length==0||matrix[0].length==0||word.length()>matrix.length*matrix[0].length)return false;
        int row=matrix.length,col=matrix[0].length;
        this.vis=new boolean[row][col];
        this.matrix=matrix;
        this.word=word;

        for(int i=0;i<row;++i){
            for(int j=0;j<col;++j){
                if(matrix[i][j]==word.charAt(0)){
                    vis[i][j]=true;
                    dfs(i,j,0);
                    if(res)return true;
                    vis[i][j]=false;
                }
            }
        }
        return res;
    }
}
